The invention generally relates to digital communication and in particular to methods, systems, and computer program products for sequentially decoding a received data signal.
With the spectacular evolution of electronic devices and the emergence of computing technologies, wireless networks are becoming essential components of all modern modes of communications. The deployment of such communication systems comes with the challenge of meeting a number of constraints related, on the one hand, to the scarcity of physical resources, such as bandwidth and, on the other hand, to hardware complexity costs required to implement the coding operations and decoding algorithms necessary to support the quality of service requirements.
Different wireless communication systems are available today, such as the cellular and wireless ad-hoc networks accommodating single or multiple transmitters/receivers using single or multiple antennas, such as MIMO (Multiple INPUT Multiple OUTPUT) systems.
In addition to low-power consumption and memory requirements imposed by the system devices, a major challenge of such communication systems is the complexity cost. In order to warrant the deployment for real-time and high-throughput applications, it is desirable that the coding operations and decoding algorithms satisfy the prescribed computational complexity which is fixed for a given device and application.
Decoding methods such as “Maximum Likelihood” decoding (also called “ML” decoding) are known to decode a digital stream in any transmission scheme. Such decoding methods provide an estimation of the closest vector to the observed received signal under the minimization of a Euclidean distance criterion. Such ML decoding techniques use an exhaustive search and provide optimal performance. However, they require a high complexity that increases as the size of the constellation codebook or the number of the transmit antennas becomes higher, thereby making the implementation of such techniques impossible in practical systems.
Other decoding techniques have been proposed to properly decode the received signal while considering the decoder complexity, such as the Sphere Decoder (E. Viterbo and J. Boutros. A universal lattice code decoder for fading channels. IEEE Transactions on Information Theory, 45(5):1639-1642, July 1999) or the Schnorr-Euchner decoder (C. P. Schnorr and M. Euchner. Lattice basis reduction: Improved practical algorithms and solving subset sum problems. In Math. Programming, pages 181-191, 1993). A main drawback of these decoders is their increasing complexity when the constellation size or the number of antennas increases. Other suboptimal low-complexity decoders, such as the ZF, the ZF-DFE and the MMSE are implemented in practical systems but present limited computational capabilities.
Other decoding algorithms applicable in linear communication systems, using single or multiple users and/or antennas, include the lattice sequential decoders which are of great interest. Lattice sequential decoding techniques (also known as “stack” decoding techniques) implement the optimal ML detection criterion using a tree representation of the ML optimization problem (decoding tree) and a tree search, which results in a reduced complexity with respect to the exhaustive search approach. In the decoding tree, each path from the root node to a leaf node is a possible transmitted signal. Nodes in the decoding tree correspond to different values taken by the decoded symbols and each path from the root node to a leaf node is a possible transmitted signal.
According to the search strategy implemented by sequential decoders, the expanded tree nodes are stored in a global stack. In the global stack, the tree nodes expanded during the decoding process are stored and sorted according to an increasing order of their decoding metrics.
Sequential decoders include decoders implementing a Best-First tree search such as the Stack decoder as disclosed in:    A. R. Murugan, H. El-Gamal, M.-O. Damen, and G. Caire. A unified framework for tree search decoding: Rediscovering the sequential decoder. IEEE Transactions on Information Theory, 52(3):933-953, March 2006;    F. Jelinek. Fast sequential decoding algorithm using a stack. IBM J. Res. Dev., 13(6):675-685, November 1969.
Another type of lattice sequential decoding method using a Best-First tree search is known as the Fano decoding method as disclosed in R. Fano. A heuristic discussion of probabilistic decoding. IEEE Transactions on Information Theory, 9(2):64-74, April 1963).
Sequential decoders improve the overall decoding complexity. However, for an increasing constellation size and a high number of antennas, the stack decoding technique requires a high computational complexity. In order to reduce this complexity, another decoding technique referred to as the Spherical-Bound Stack decoder (SB-Stack) has been proposed in the article by G. R. Ben-Othman, R. Ouertani, and A. Salah, entitled “The Spherical Bound Stack Decoder”, In Proceedings of International Conference on Wireless and Mobile Computing, pages 322-327, October 2008. The SB-stack approach combines the Stack search strategy with the Sphere Decoder search region: the decoder searches for the closest vector inside a sphere centered at the received point implementing the stack decoding strategy. The spherical search region imposes a search interval for each detected symbol. Only nodes belonging to these intervals at each tree level are visited and expanded.
Lattice sequential decoders have strongly imposed themselves as optimal detection schemes in linear wireless communication systems reducing the optimal ML decoding problem to the search for the path in a graph-tree having the least weight metric. However, in presence of a large constellation size (equivalently a large number of nodes in each tree level) and/or high dimensional-decoding tree, the number of the visited nodes during the tree-search phase, and thus the size of the stack storing these nodes, increases and may exceed the available stack size imposed by the hardware requirements for a given target application and given devices. The stack size may also be exceeded when the communication channel is bad requiring a slowest convergence time and longer decoding process for visiting a high number of tree-nodes until finding the desired estimation of the original information symbols.
Such rapid growth of the stack size in presence of high-dimensional constellations and/or tree-levels, as well as the resulting complexity in finding the optimal path in the graph, are of significant impediments to the implementation of the lattice sequential algorithms for real-time and high-throughput applications constrained by limited physical resources (such as a limited stack size imposed by the hardware requirements).
Accordingly, improved sequential decoding systems, methods, and computer program products are needed that enable stack management.